/*
	矩阵连乘,寻找最小的划分点

	m[i][i] = 0  i = j
	        = min{m[i][k] + m[k+1][j] + (i-1)jk}
*/

int matrixChain(int *p, int n, int **m, int **s)
{//n为矩阵的个数,即p.length-1
	int i,j,r,k;

	for (i = 0; i < n; i++)
	{
		m[i][i] = 0;//m[i][i]即 i=j 单一矩阵
	}

	//r为连乘个数
	for (r = 2; r <=n; r++)
	{
		for (i = 0; i <= n-r; i++)//i为连乘矩阵的第一个
		{
			j = i + r - 1;//j为连乘的最后一个
			m[i][j] = 32767;

			for (int k = i; k <= j - 1; k++)
			{//寻找合适的断开点
				int tmp = m[i][k] + m[k+1][j] + p[i]p[k+1]p[j+1];
				if (tmp < m[i][j])
				{
					m[i][j] = tmp;
					s[i][j] = k;
				}
					
			}

		}
	}
	return m[0][n - 1];//返回最小计算个数
}

void printChain(int i, int j, char **a, int **s)
{
	if (i == j)
	{
		printf("%s", a[i]);
	}
	else
	{
		printf("(");
		printChain(i,s[i][j],a,s);
		printChain(s[i][j]+1,j,a,s);
		printf(")");
	}
}